package com.shixianjun;

import com.shixianjun.tools.Tools;

/**
 * 一串连续的明牌（正整数数组）两个玩家轮流取牌，但只能拿最左侧的牌或者最右侧的牌 点数相加多的玩家获胜 求获胜者的点数和
 * */
public class 纸牌游戏 {
    public static void main(String[] args) {
        int[] arr = Tools.randomIntArray(31, 30);
//        int[] arr = {2,3,48,7,99,1,3,77};
        Tools.printIntArray("牌面：", arr);
        System.out.printf("获胜者分数：%d \n", maxValue1(arr));
        System.out.printf("获胜者分数：%d \n", maxValue2(arr));
    }

    public static int maxValue1(int[] values) {
        long start = System.currentTimeMillis();
        int xian = xian1(values, 0, values.length - 1);
        int hou = hou1(values, 0, values.length - 1);
        long end = System.currentTimeMillis();
        System.out.print("maxValue1耗时: " + (end - start) + "毫秒\n");
        return Math.max(xian, hou);
    }
    public static int xian1(int[] values, int L, int R) {
        if (L == R) {
            return values[L];
        }

        if (L == R - 1) {
            return Math.max(values[L], values[R]);
        }

        // 拿左侧的牌
        int v1 = values[L] + hou1(values, L + 1, R);
        int v2 = values[R] + hou1(values, L, R - 1);

        return Math.max(v1, v2);
    }

    public static int hou1(int[] values, int L, int R) {
        if (L == R) {
            return 0;
        }
        if (L == R - 1) {
            return Math.min(values[L], values[R]);
        }
        int v1 = xian1(values, L + 1, R);
        int v2 = xian1(values, L, R - 1);

        return Math.min(v1, v2);
    }


    public static int maxValue2(int[] values) {

        long start = System.currentTimeMillis();

        int[][] xiandp = new int[values.length][values.length];
        int[][] houdp = new int[values.length][values.length];

        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length; j++) {
                xiandp[i][j] = -1;
                houdp[i][j] = -1;
            }
        }

        int xian = xian2(values, 0, values.length - 1, xiandp, houdp);
        int hou = hou2(values, 0, values.length - 1, xiandp, houdp);

        long end = System.currentTimeMillis();
        System.out.print("maxValue2耗时: " + (end - start) + "毫秒\n");

        return Math.max(xian, hou);
    }

    public static int xian2(int[] values, int L, int R, int[][] xiandp, int[][] houdp) {

        if (xiandp[L][R] != -1) {
            return xiandp[L][R];
        }

        int ans = 0;
        if (L == R) {
            ans = values[L];
        } else if (L == R - 1) {
            ans = Math.max(values[L], values[R]);
        } else {
            // 拿左侧的牌
            int v1 = values[L] + hou2(values, L + 1, R, xiandp, houdp);
            int v2 = values[R] + hou2(values, L, R - 1, xiandp, houdp);

            ans = Math.max(v1, v2);
        }

        xiandp[L][R] = ans;
        return ans;
    }

    public static int hou2(int[] values, int L, int R, int[][] xiandp, int[][] houdp) {

        if (houdp[L][R] != -1) {
            return houdp[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = 0;
        } else if (L == R - 1) {
            ans = Math.min(values[L], values[R]);
        } else  {
            int v1 = xian2(values, L + 1, R, xiandp, houdp);
            int v2 = xian2(values, L, R - 1, xiandp, houdp);

            ans = Math.min(v1, v2);
        }
        houdp[L][R] = ans;
        return ans;
    }
}
